class Solution {
public:
    string minWindow(string s, string t) {

        int m = s.size(), n=t.size();
        int l=-1, r=-1;
        int left=0, right=0;
        int count = 0;

        unordered_map<char, int> keys;
        for(int i=0; i<n; i++){
            keys[t[i]]++;
        }
        unordered_map<char, vector<int>> key_pos;
        
        for(; right< m; ){
            // cout<< s[right] << endl;

            if(keys.count(s[right])){
                
                if(key_pos[s[right]].size() >= keys[s[right]]){
                    key_pos[s[right]].back() = right;
                }
                else{
                    key_pos[s[right]].push_back(right);
                    count++;
                }
            }

            if(count == n){
                
                left = INT_MAX;
                for(auto it: key_pos){
                    for(auto itt: it.second){
                        left = min(left, itt);
                    } 
                }
                key_pos[s[left]].pop_back();
                count--;
                if(right-left < r-l || l==-1){
                    l = left;
                    r = right;
                }
            }
            // cout<< l << '\t' << r << '\t'<< left << '\t' << right << '\t' << count << endl;
            right++;
        }

        // cout<< l << '\t' << r << endl;
      
        if(l == -1 || r == -1) return "";
        return string(s, l, r-l+1);
    }
};